This is how scaling ability of algorithms are described.
Let’s assume we are dealing with algorithms that take a list of n items.
For example, an algorithm that just iterates the list and returns the greatest item.
This algorithm only needs to do a simple iteration to know the results, and if we double n, the execution time also doubles.
If we tried to describe the mathematical function ExecutionTime(n) of that algorithm, the equation should look something like this:
execution_time = n * constant constant includes any computation in the algorithm that doesn’t change when increasing the size of the list (n).
We only care about how n directly affects the execution_time
The scalability of this equation depends proportionally on n, so to describe its complexity we use the Big O notation. In this example, its time complexity is O(n), and it tells us that the execution time will change proportionally to (n).
If the execution_time equation had multiple complexities, e.g. = 2n + n², we would only describe the biggest complexity (the one that increases faster), in this example it would be z² since it dominates more and more as n increases, so in Big O notation it would be O(n²)
If an algorithm has a time complexity of O(n), and we increase the size of n by 10x, we should expect the execution time to also increase by 10x. But if the algorithm is O(n²), we should expect the execution time to increase by 100x instead, because 10² = 100
An example of an O(n²) algorithm:
Produce all the ordered combinations of pairs from a list of n items. E.g.: input = [A,B,C], which is size: 3
output = [[A,A], [A,B], [A,C], [B,A], [B,B], [B,C], [C,A], [C,B], [C,C]], which is size: 9 (3²)
O(1), its equation looks like this: execution_time = constant, because no matter how many more items you add, it will always take the same amount (constant) to run
O(log n), its equation looks like this: execution_time = log(n) * constant, if you increase n by 1024x, the execution time increases by just 10x (log₂(1024) = 10)
O(n²), its equation looks like this: execution_time = n² * constant, if you increase n by 3x, the execution time increases by 9x (3² = 9).
Big O notation describes the upper bound of the time complexity.
There are other notations that describe the lower bound, or both bounds:
Ω(n), describes the lower bound of the time complexity.n items, and returns the first item that matches a condition.O(1), but if the first item doesn’t match the condition, the execution time will be O(n).Ω(1), because it will never be slower than O(1)Θ(n), describes both the upper and lower bounds of the time complexity.In general, these notations are called Asymptotic Notations